home *** CD-ROM | disk | FTP | other *** search
/ Acorn User: China / Acorn User China CD-ROM (UK) (Disc B) / Acorn User China CD-ROM (UK) (Disc B).bin / STUTTGART / FROMUTS / UNIXLIB37B / src_c_alloc < prev    next >
Encoding:
C/C++ Source or Header  |  1993-02-10  |  5.6 KB  |  378 lines
  1. static char sccs_id[] = "@(#) alloc.c 5.0 "__DATE__" HJR";
  2.  
  3. /* alloc.c (c) Copyright 1990 H.Rogers */
  4.  
  5. /* features multiple free lists hashed on block size */
  6.  
  7. #include <stddef.h>
  8. #include <stdlib.h>
  9. #include <string.h>
  10.  
  11. #ifdef M_DEBUG
  12. #include <stdio.h>
  13. #include <signal.h>
  14.  
  15. static int __m_fail(char *exp,char *file,int line)
  16. {
  17. fprintf(stderr,"\n\"%s\", line %d: Assertion failed: %s\n",file,line,exp);
  18. raise(SIGABRT);
  19. return(0);
  20. }
  21.  
  22. #define assert(x)    (void)((x) ? 0 : __m_fail(#x,__FILE__,__LINE__))
  23.  
  24. #define addr(x)     ((x) ? (*((int *)(x)) | 1) : 0)
  25.  
  26. #define MAGIC        0x4349474d
  27. #endif
  28.  
  29. extern void *sbrk(int);
  30.  
  31. typedef struct _blk
  32.   {
  33. #ifdef M_DEBUG
  34.   int        magic;
  35. #endif
  36.   struct _blk    *next;
  37.   size_t    size;
  38.   } blk;
  39.  
  40. #ifdef M_DEBUG
  41. #define BLKSIZ        16    /* smallest power of 2 >= sizeof(blk) */
  42. #else
  43. #define BLKSIZ        8
  44. #endif
  45.  
  46. #define blkalign(x)    (((x) + (BLKSIZ<<1) - 1) & (~(BLKSIZ - 1)))
  47.  
  48. #define NFL    8
  49.  
  50. static blk __fl[NFL];
  51. static size_t __flmin[NFL] =
  52.   {
  53.   4096    + BLKSIZ,
  54.   1024    + BLKSIZ,
  55.   256    + BLKSIZ,
  56.   64    + BLKSIZ,
  57.   32    + BLKSIZ,
  58.   16    + BLKSIZ,
  59.   8    + BLKSIZ,
  60.   0    + BLKSIZ    /* catchall */
  61.   };
  62.  
  63. #define MEMINC        12    /* sbrk() memory block bit alignment */
  64.  
  65. void __allocinit(void)
  66. {
  67. register blk *b;
  68. register int i;
  69.  
  70. #ifdef M_DEBUG
  71. assert(sizeof(struct _blk) <= BLKSIZ);
  72. #endif
  73.  
  74. for (i = 0; i < NFL; i++)
  75.   {
  76.   b = __fl + i;
  77.   b->next = b;
  78.   b->size = BLKSIZ;
  79. #ifdef M_DEBUG
  80.   b->magic = MAGIC;
  81. #endif
  82.   }
  83. }
  84.  
  85. static blk *findblk(register int i,register blk *a)
  86. {
  87. register blk *b,*p;
  88.  
  89. p = __fl + i;
  90. b = p->next;
  91.  
  92. #ifdef M_DEBUG
  93. assert(addr(p));
  94. assert(p->magic == MAGIC);
  95. #endif
  96.  
  97. while (b > p)
  98.   {
  99. #ifdef M_DEBUG
  100.   assert(addr(b));
  101.   assert(b->magic == MAGIC);
  102. #endif
  103.   if (b >= a) break;
  104.   p = b;
  105.   b = b->next;
  106.   }
  107.  
  108. return(p);
  109. }
  110.  
  111. #define addblk(i,n,p) ((n)->next = (p)->next,(p)->next = (n))
  112.  
  113. #define delblk(i,b,p) ((p)->next = (b)->next)
  114.  
  115. static void concatblk(register blk *a,register blk *p)
  116. {
  117. register blk *b;
  118.  
  119. if (!p) return;
  120.  
  121. b = p->next;
  122.  
  123. while ((char *)a + a->size == (char *)b)
  124.   {
  125.   a->size += b->size;
  126. #ifdef M_DEBUG
  127.   b->magic = 0;
  128. #endif
  129.   b = b->next;
  130.   }
  131.  
  132. p->next = b;
  133. }
  134.  
  135. static int flindex(register int size)
  136. {
  137. register int i;
  138.  
  139. for (i = 0; size < __flmin[i]; i++);
  140.  
  141. return(i);
  142. }
  143.  
  144. static blk *findsize(register int i,register int size,register blk **p_)
  145. {
  146. register blk *b,*p;
  147.  
  148. p = __fl + i;
  149. b = p->next;
  150.  
  151. while (b > p)
  152.   {
  153.   if (b->size >= size)
  154.     { delblk(i,b,p); break; }
  155.   p = b;
  156.   b = b->next;
  157.   }
  158.  
  159. if (p_) *p_ = p; return(b);
  160. }
  161.  
  162. void *malloc(register size_t size)
  163. {
  164. register blk *b;
  165. register int i;
  166. blk *p;
  167.  
  168. if (!size) return(0);
  169.  
  170. size = blkalign(size);
  171.  
  172. i = flindex(size);
  173.  
  174. b = findsize(i,size,&p);
  175.  
  176. if (b <= p)
  177.   {
  178.   register void *m;
  179.   register int _size;
  180.  
  181.   _size = ((size>>MEMINC) + 1)<<MEMINC;
  182.   if ((m = sbrk(_size)) == (void *)-1) return(0);
  183.  
  184.   if ((char *)p + p->size == (char *)m)
  185.     {
  186.     b = p;
  187.     p = findblk(i,b);
  188.     delblk(i,b,p);
  189.     b->size += _size;
  190.     }
  191.   else
  192.     {
  193.     b = (blk *)m;
  194.     b->size = _size;
  195. #ifdef M_DEBUG
  196.     b->magic = MAGIC;
  197. #endif
  198.     }
  199.   }
  200.  
  201. #ifdef M_DEBUG
  202. assert(addr(b));
  203. assert(b->magic == MAGIC);
  204. #endif
  205.  
  206. if (b->size > (size + __flmin[i]))
  207.   {
  208.   register blk *n;
  209.  
  210.   n = (blk *)((char *)b + size);
  211.  
  212.   addblk(i,n,p);
  213.  
  214.   n->size = b->size - size;
  215. #ifdef M_DEBUG
  216.   n->magic = MAGIC;
  217. #endif
  218.   b->size = size;
  219.   }
  220.  
  221. return((void *)((char *)b + BLKSIZ));
  222. }
  223.  
  224. void *realloc(register void *_a,register size_t size)
  225. {
  226. register blk *a;
  227. register int i;
  228. blk *p;
  229.  
  230. if (!(_a)) return(malloc(size));
  231.  
  232. if (!size) { free(_a); return(0); }
  233.  
  234. size = blkalign(size);
  235.  
  236. #ifdef M_DEBUG
  237. assert(addr(_a));
  238. #endif
  239.  
  240. a = (blk *)((char *)_a - BLKSIZ);
  241.  
  242. #ifdef M_DEBUG
  243. assert(addr(a));
  244. assert(a->magic == MAGIC);
  245. #endif
  246.  
  247. i = flindex(a->size);
  248.  
  249. p = findblk(i,a);
  250.  
  251. concatblk(a,p);
  252.  
  253. if (a->size < size)
  254.   {
  255.   if ((char *)p + p->size == (char *)a && p->size + a->size >= size)
  256.     {
  257.     register blk *b;
  258.  
  259. #ifdef M_DEBUG
  260.     assert(addr(p));
  261.     assert(p->magic == MAGIC);
  262. #endif
  263.     b = p;
  264.     p = findblk(i,b);
  265.     delblk(i,b,p);
  266.     b->size += a->size;
  267. #ifdef M_DEBUG
  268.     a->magic = 0;
  269. #endif
  270.     memmove((char *)b + BLKSIZ,_a,a->size - BLKSIZ);
  271.     _a = (char *)(a = b) + BLKSIZ;
  272.     }
  273.   else
  274.     {
  275.     register void *m;
  276.     register int _size;
  277.  
  278.     _size = ((size>>MEMINC) + 1)<<MEMINC;
  279.     if ((m = sbrk(_size)) == (void *)-1) return(0);
  280.  
  281.     if ((char *)a + a->size == (char *)m)
  282.       a->size += _size;
  283.     else
  284.       {
  285.       register blk *b;
  286.  
  287.       addblk(i,a,p);
  288.       b = (blk *)m;
  289.       b->size = _size;
  290. #ifdef M_DEBUG
  291.       b->magic = MAGIC;
  292. #endif
  293.       memcpy((char *)b + BLKSIZ,_a,a->size - BLKSIZ);
  294.       _a = (char *)(a = b) + BLKSIZ;
  295.       }
  296.     }
  297.   }
  298.  
  299. i = flindex(size);
  300.  
  301. if (a->size > (size + __flmin[i]))
  302.   {
  303.   register blk *n;
  304.  
  305.   p = findblk(i,a);
  306.  
  307.   n = (blk *)((char *)a + size);
  308.  
  309.   addblk(i,n,p);
  310.  
  311.   n->size = a->size - size;
  312. #ifdef M_DEBUG
  313.   n->magic = MAGIC;
  314. #endif
  315.   a->size = size;
  316.   }
  317.  
  318. return(_a);
  319. }
  320.  
  321. void free(register void *_a)
  322. {
  323. register blk *a,*p;
  324. register int i;
  325.  
  326. if (!_a) return;
  327.  
  328. #ifdef M_DEBUG
  329. assert(addr(_a));
  330. #endif
  331.  
  332. a = (blk *)((char *)_a - BLKSIZ);
  333.  
  334. #ifdef M_DEBUG
  335. assert(addr(a));
  336. assert(a->magic == MAGIC);
  337. #endif
  338.  
  339. i = flindex(a->size);
  340.  
  341. p = findblk(i,a);
  342.  
  343. concatblk(a,p);
  344.  
  345. if ((char *)p + p->size == (char *)a)
  346.   {
  347.   p->size += a->size;
  348. #ifdef M_DEBUG
  349.   a->magic = 0;
  350. #endif
  351.   }
  352. else
  353.   addblk(i,a,p);
  354. }
  355.  
  356. #ifdef M_DEBUG
  357. void __m_debug(void)    /* dump free lists */
  358. {
  359. register blk *b;
  360. register int i;
  361.  
  362. for (i = 0; i < NFL; i++)
  363.   {
  364.   printf("\nfl: %d ( >= %d )\n",i,__flmin[i] - BLKSIZ);
  365.   b = __fl + i; do
  366.     {
  367.     b = b->next;
  368.     printf("%7x: next: %7x [%7x] size: %x\n",b,b->next,
  369.     (char *)b + b->size,b->size - BLKSIZ);
  370.     assert(addr(b));
  371.     assert(b->magic == MAGIC);
  372.     }
  373.   while (b->next > b);
  374.   }
  375. putchar('\n');
  376. }
  377. #endif
  378.